package levelorder;

import entity.TreeNode;

import java.util.LinkedList;

public class MinDepth {
    /*
    * 111. 二叉树的最小深度
    * 给定一个二叉树，找出其最小深度。
    * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    * 说明：叶子节点是指没有子节点的节点。
    * */
    public static void main(String[] args){
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        MinDepth o = new MinDepth();
        o.mySolution(root);
    }

    // 我的想法：层序遍历完后得知深度，由于要求最小深度，此时广度优先最合适，深度优先需要遍历完所有节点
    public int mySolution(TreeNode root){
        if(root == null)
            return 0;
        int depth = 0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                root = deque.pop();
                // 判断是不是叶子节点
                if(root.left == null && root.right == null)
                    return ++depth;
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
                len--;
            }
            depth++;
        }
        return depth;
    }

    // 递归法
    // 这里有一个陷阱，当root的左儿子为null，右儿子不为null时，返回的是0，然后最小就一定为1
    // 采进这个陷阱的原因是，没有判断该节点是不是叶子节点，上述情况的节点明显不是叶子节点
    // 只有是叶子节点，才返回min（left， right）
    private int minDepth(TreeNode root){
        if(root == null)
            return 0;

        int left = minDepth(root.left);
        int right = minDepth(root.right);
        // 以下是，不是叶子节点的情况
        if(root.left == null && root.right != null)
            return right + 1;
        if(root.right == null && root.left != null)
            return left + 1;

        return Math.min(left, right) + 1;
    }
}
